#include "LinkTree.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define true 1
#define false 0

 
LTNode *CreateTreeNode(ElementType element)
{
    LTNode *newNode=(LTNode *)malloc(sizeof(LTNode));
    if(newNode==NULL)
    {
        printf("creat malloc error!\n");
        return NULL;
    }
    newNode->data=element;
    newNode->firstChild=NULL;
    newNode->nextSibling=NULL;
    newNode->parent=NULL;
    return newNode;
}


void ConnectBranch(LTNode *parent, LTNode *child)
{
    //判断空指针
    if(parent==NULL||child==NULL)
    {
        return;
    }
    //连接
    child->nextSibling=parent->firstChild;
    parent->firstChild=child;
    child->parent=parent;
}


void DisConnectBranch(LTNode *parent, LTNode *child)
{
    if(parent==NULL||child==NULL||parent->firstChild==NULL)
    {
        return;
    }

    LTNode *travelPoint=parent->firstChild;//遍历
    if(travelPoint=child)
    {
        parent->firstChild=child->nextSibling;
        child->parent=NULL;
        child->nextSibling=NULL;//断开连接的节点要置为空
        return;
    }
    
    while(travelPoint->nextSibling!=NULL)//遍历兄弟节点
    {
        if(travelPoint->nextSibling==child)//查找child
        {
            travelPoint->nextSibling=child->nextSibling;
            child->parent=NULL;
            child->nextSibling=NULL;
            return;
        }
        travelPoint=travelPoint->nextSibling;//继续查找下一个兄弟节点
    }
}
void FreeNode(LTNode *treeNode)
{
    if(treeNode==NULL)
    return;

    FreeNode(treeNode->firstChild);//递归 重复调用函数
    FreeNode(treeNode->nextSibling);
    free(treeNode);
    //LTNode *travelPoint=treeNode->firstChild;//遍历
    // while(travelPoint!=NULL)
    // {
    //     LTNode *nextNode=travelPoint->nextSibling;//查找兄弟节点
    //     FreeNode(travelPoint);//释放重置指针
    //     travelPoint=nextNode;//返回上一个节点
    // }
    // free(treeNode);
}
int InitLTree(LTree *tree)
{
    struct UniversalType typedata={NULL,-1};//初始化将结构体指针置为空
    tree->root=CreateTreeNode(typedata);//将置空结构体赋予树节点
    if(tree->root==NULL)//判断节点是否为空
    {
        return false;
    }
    else
    {
        return true;
    }
}

void FreeTree(LTree *tree)
{
    FreeNode(tree->root);//释放树节点
    tree->root=NULL;//树节点置为空
}

int GetNodeHeight(LTNode *treeNode)
{
    if(treeNode==NULL)
    return 0;
    int height=0;
    LTNode *travelPoint=treeNode->firstChild; //  遍历孩子个数                  
    while(travelPoint!=NULL)
    {
        int childHeight=GetNodeHeight(travelPoint);//把孩子个数传给高度
        height=height>childHeight?height:childHeight;//比较节点高度，取高值保存下来
        travelPoint=travelPoint->nextSibling;//寻找下一个兄弟节点
    }
    return height+1;//加上首节点
}
int GetTreeHeight(LTree *tree)
{
   
    return GetNodeHeight(tree->root);//调用函数取树高
}

LTNode* FindNode(LTNode *node,ElementType element,int (*func)(ElementType,ElementType))
{
    if(node==NULL)
    return NULL;
    if(func!=NULL&&func(node->data,element)==true)//判断首节点是否为要找的值且不为空
    {
        return node;
    }
    // if(strcmp(node->data,element)==0)
    // {
    //     return node;
    // }

    LTNode *childNode=node->firstChild;
    LTNode *targetNode=NULL;
    // while(childNode!=NULL)
    // {
    //     targetNode=FindNode(childNode,element);
    //     if(targetNode!=NULL)
    //     {
    //         return targetNode;
    //     }
    //     childNode=childNode->nextSibling;
    // }
    if((targetNode=FindNode(node->firstChild,element,func))!=NULL)//查找孩子节点
    {
        return targetNode;
    }
    if((targetNode=FindNode(node->nextSibling,element,func))!=NULL)//查找兄弟节点
    {
        return targetNode;
    }
    return targetNode;
}

LTNode *FindTreeNode(LTree *tree,ElementType element, int (*func)(ElementType,ElementType))
{
    
    return FindNode(tree->root,element,func);//调用函数查找节点
}

void TravelTreeNode(LTNode *node,int deepth,void(*func)(ElementType ))
{
    if(node==NULL)
    return;
    if(func!=NULL)
    {
        func(node->data);
    }
    // for(int i=0;i<deepth;i++)
    // printf(" ");
    // if(node->parent!=NULL)
    // printf("|_");
    // printf("%s\n",node->data);

    // LTNode *travelPoint=node->firstChild;
    // while(travelPoint!=NULL)
    // {
    //     TravelTreeNode(travelPoint);
    //     travelPoint=travelPoint->nextSibling;
    // }
    TravelTreeNode(node->firstChild,deepth+1,func);//回调遍历函数
    TravelTreeNode(node->nextSibling,deepth,func);
}
void Travel(LTree *tree,void(*func)(ElementType ))
{
    TravelTreeNode(tree->root,0,func);
}
